//
// Created by DengLibin on 2018/12/16 0016.
//
/**
 * 排序
 */

#include <iostream>
using namespace std;

/*
	排序算法的稳定性：
			假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，
		即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；
		否则称为不稳定的。
*/
#define LEN 10 //数组长度
int arr[LEN] = {9,23,3,24,234,45,223,452,345,4};

void swap_(int * a, int * b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void showArr(int * argArr, int len)
{
    cout << "数组:";
    for (int i = 0; i < len; i++)
    {
        std::cout << argArr[i] << ",";
    }
}
//选择排序(非稳定排序) O(n^2)
void selectSort()
{
    for (int i = 0; i < LEN -1; i++)
    {
        for (int j = i + 1; j < LEN; j++)
        {
            if (arr[i] > arr[j])
            {
                swap_(arr+i,arr+j);
            }
        }
    }
}
//冒泡排序（稳定排序）O(n^2)
void popSort()
{
    for (int i = 0; i < LEN; i++)
    {
        for (int j = 0; j < LEN - i -1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap_(arr + j, arr + j + 1);
            }
        }
    }
}
//插入排序（稳定排序）O(n^2)
void insertSort()
{
    for (int i = 0; i < LEN; i++) //后一个数
    {
        for (int j = 0; j < i; j++) //前面已经排好序的数
        {
            if (arr[i] < arr[j])
            {
                swap_(arr+i,arr+j);
            }
        }
    }
}
//合并
void merge(int *arr, int startIndex, int middleIndex, int endIndex)
{

    int len = (endIndex - startIndex + 1);

    int *temp = new int[len];
    int i = startIndex;//左序列指针
    int j = middleIndex + 1;//右序列指针
    int t = 0;//临时数组指针
    while (i <= middleIndex && j <= endIndex)
    {
        if (arr[i] <= arr[j])
        {
            temp[t++] = arr[i++];
        }
        else
        {
            temp[t++] = arr[j++];

        }
    }
    while (i <= middleIndex) //将左边剩余元素填充进temp中
    {

        temp[t++] = arr[i++];
    }

    while (j <= endIndex) ////将右序列剩余元素填充进temp中
    {
        temp[t++] = arr[j++];
    }
//	showArr(temp, len);

    //将temp中的元素全部拷贝到原数组中
    for (int i = 0; i < t; i++)
    {
        arr[startIndex + i] = temp[i];
    }

    delete[] temp;
}


//归并
void guiBing(int *arr, int startIndex, int endIndex)
{
    if (startIndex < endIndex)
    {
        int middle = (startIndex + endIndex) / 2;
        guiBing(arr, startIndex, middle);
        guiBing(arr, middle + 1, endIndex);
        merge(arr, startIndex, middle, endIndex);
    }
}
//归并排序（稳定排序）O(nlogn)
void guiBingSort()
{
    guiBing(arr, 0, LEN - 1);
}


void quick(int left, int right)
{
    if (left > right)
    {
        return;
    }
    int i = left; //左指针
    int j = right; //右指针
    int temp = arr[left]; //基数

    while (i != j)
    {
        // //顺序很重要，要先从右边开始找
        while (arr[j] >= temp && j > i) //右指针左移
        {
            j--;
        }
        while (arr[i] <= temp && i < j) //左指针右移
        {
            i++;
        }
        if (i < j)
        {
            swap_(arr+i,arr+j); //交换
        }
    }
    //交换基数和arr[i] / arr[j]
    arr[left] = arr[i];
    arr[i] = temp;

    //递归
    quick(left, i - 1);
    quick(i + 1, right);
}

//快速排序
void quickSort()
{
    quick(0,LEN-1);
}



int main42(void)
{
    //selectSort(); //选择排序
    //popSort(); //冒泡排序
    //insertSort(); //插入排序
    //guiBingSort();//归并排序
    quickSort(); //快速排序
    showArr(arr,LEN);
    return 0;
}